package sackknap;

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
import javax.swing.*;

/**
 *
 * @author Kristian & Erik
 */
public class Sackknap {

    //The inread file
    public ArrayList<SackknapObject> listOfItems = new ArrayList<SackknapObject>();
    //The best way to pack the sack
    public ArrayList<SackknapObject> bestList = new ArrayList<SackknapObject>();
    public ArrayList<SackknapObject> tempList = new ArrayList<SackknapObject>();
    public int capacity, maxValue, loops = 0;

    public Sackknap() throws FileNotFoundException, IOException {
        String file = JOptionPane.showInputDialog("Which set do you want to run?" +
                "\n-reference\n-knapsack\n-knapsack2\n-knapsack3");
        readFile(file);

        dynamic(listOfItems);

        System.out.println(bestList.toString());
    }

    public void readFile(String f) throws FileNotFoundException, IOException {
        //if the given filename is invalid, execute the reference file
        if (!((f.contains("knapsack")) || (f.contains("reference")))) {
            f = "reference";
        }
        Scanner sc = new Scanner(new FileReader(f + ".txt"));
        String temp = "";
        while (sc.hasNext()) {
            temp = sc.next();
            if (!(temp.contains("capacity"))) {
                listOfItems.add(parseText(temp));
            } else {
                capacity = Integer.parseInt("" + (temp.substring(temp.indexOf("=") + 1)));
            }
        }
    }

    //method to pick the size and the value and store them as SackknapObjects
    //from the inread-file
    public SackknapObject parseText(String s) {
        String value = "", size = "";
        int i = 1;
        while (s.charAt(i) != ',') {
            size += s.charAt(i);
            i++;
        }
        i++;
        while (s.charAt(i) != ')') {
            value += s.charAt(i);
            i++;
        }
        return new SackknapObject(Integer.parseInt(size), Integer.parseInt(value));
    }

    public void dynamic(ArrayList<SackknapObject> list){
        
        int[][] two = new int[list.size()+1][capacity+1];
        //runs through all the objects
        for(int i = 1; i <= list.size(); i++){
            //runs through all the capacitys
            for(int k = 1; k <= capacity; k++){
                //checks if the current object is larger than the current capacity,
                //then sets the last set och objects as the opimal
                if (list.get(i - 1).getSize() > k) {
                    two[i][k] = two[i - 1][k];
                }
                //if it is smaller than the current capacity,
                //takes the maximum of either the last set of objects or the current
                //objet in combination with the last set of objects that foremed the
                //optimal solution for that combinatio(objects and capacity)
                else {
                    two[i][k] = Math.max(two[i - 1][k], list.get(i - 1).getValue() + two[i - 1][k - list.get(i - 1).getSize()]);
                }
            }
        }

        //so it is really empty
        bestList.clear();
        //Goes through the hole list(two)and picks out only the elements in the optimal solution
        int K = capacity;
        for (int i = list.size(); i >= 1; i--) {
            if (two[i][K] != two[i - 1][K]) {
                bestList.add(list.get(i - 1));
                K -= list.get(i - 1).getSize();
            }
        }
    }

    //sums the combined _value_ of our given list
    public int sumValue(ArrayList<SackknapObject> a) {
        int temp = 0;
        for (int i = 0; i < a.size(); i++) {
            temp += a.get(i).getValue();
        }
        return temp;
    }
    //sums the combined _size_ of our given list

    public int sumSize(ArrayList<SackknapObject> a) {
        int temp = 0;
        for (int i = 0; i < a.size(); i++) {
            temp += a.get(i).getSize();
        }
        return temp;
    }

    public static void main(String[] args) throws FileNotFoundException, IOException {
        new Sackknap();
    }
}
